package leetcode_1901_2000;

import java.util.Arrays;

public class LeeCode_1986 {
    public static void main(String[] args) {
        System.out.println(minSessions(new int[]{1, 2, 3}, 3));
        System.out.println(minSessions(new int[]{3,1,3,1,1}, 8));
        System.out.println(minSessions(new int[]{1,2,3,4,5}, 15));
        System.out.println(minSessions(new int[]{1,3,3,4,4,4,5,6,7}, 12));
    }
    private static int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        int[] sums = new int[1 << n];
        for (int i = (1 << n) - 1, bit = i; i > 0; i = (i - 1) & bit){
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0){
                    sum += tasks[j];
                    if (sum > sessionTime){
                        break;
                    }
                }
            }
            if (sum <= sessionTime){
                sums[i] = sum;
            }
        }
        int[] f = new int[1 << n];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 1; i < (1 << n); i++) {
            for(int j = i; j > 0; j = (j - 1) & i){
                if (sums[j] != 0){
                    f[i] = Math.min(f[i], f[j ^ i] + 1);
                }
            }
        }
        return f[(1 << n) - 1];
    }
    private static int minSessions2(int[] tasks, int sessionTime) {
        int n = tasks.length;
        int[] sums = new int[1 << n];
        for (int i = (1 << n) - 1, bit = i; i > 0; i = (i - 1) & bit){
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0){
                    sums[i] += tasks[j];
                }
            }
        }
        int[] memo = new int[1 << n];
        Arrays.fill(memo, -1);
        memo[0] = 0;
        return dfs(sums, memo, (1 << n) - 1, 0, sessionTime);
    }
    private static int dfs(int[] sums, int[] memo, int now, int count, int sessionTime){
        if (memo[now] != -1)
            return memo[now] + count;
        int min = Integer.MAX_VALUE;
        for (int i = now, bit = i; i > 0; i = (i - 1) & bit){
            if (sums[i] > sessionTime){
                continue;
            }
            min = Math.min(min, dfs(sums, memo, bit ^ i, count + 1, sessionTime));
        }
        memo[now] = min - count;
        return min;
    }
}